package Top200;

import java.util.HashMap;

/**
 * @author zhangmin
 * @create 2022-02-25 11:07
 */
public class minWindow76 {
    public String minWindow(String s, String t) {
        int ns=s.length(),nt=t.length();
        if (ns<nt) return "";
        HashMap<Character,Integer> windows=new HashMap<>(),need=new HashMap<>();
        for (Character ct:t.toCharArray()) {
            need.put(ct,need.getOrDefault(ct,0)+1);
        }
        int valid=0;
        int left=0,right=0,res=Integer.MAX_VALUE;
        int start=-1;
        while (right<ns){
            char c=s.charAt(right);
            right++;
            if (need.containsKey(c)){
                windows.put(c,windows.getOrDefault(c,0)+1);
                if (windows.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            while (valid==need.size()&&left<right){
                if (right-left<res){
                    res=right-left;
                    start=left;
                }
                char d = s.charAt(left);
                if (need.containsKey(d)){
                    if (need.get(d).equals(windows.get(d))){
                        valid--;
                    }
                    windows.put(d,windows.getOrDefault(d,0)-1);
                }
                left++;
            }
        }
        return start==-1?"":s.substring(start,start+res);
    }
}
